package net.lzzy.algorithm.find;

import android.util.Pair;

public class BinaryTree <T extends Comparable<? super T>>extends BaseSearch<T>{
    private Pair<Integer,T>root;    //记录根节点
    private BinaryTree<T> left,right;  //记录左右节点

    BinaryTree(T[] itmes) {
        super(itmes);
        root=new Pair<>(0,itmes[0]);   //给根节点赋值
        for(int i=1;i<itmes.length;i++){
            addNode(new Pair<>(i,itmes[i]));
        }
    }
    private BinaryTree(Pair<Integer,T>node){   //记录空节点
     root=node;
    }

    private void addNode(Pair<Integer,T> node){
        int comp=compare(node.second,root.second);
        if (comp>0){
            if (right==null){
               right=new BinaryTree<>(node);
            }else {
                right.addNode(node);
            }
        }
        if (comp<0){
            if (right==null){
                left=new BinaryTree<>(node) ;
                }else{
                left.addNode(node);
            }
        }
    }

    private long start=-1;  //记录时间

    @Override
    public int search(T key) {
        if (start < 0) {
            start = System.currentTimeMillis();  //开始时间
        }
        int comp = compare(key, root.second);
        if (comp == 0) {
            setTime(System.currentTimeMillis() - start);
            return root.first;
        } else if (comp > 0) {
            if (right == null) {
                setTime(System.currentTimeMillis() - start);
                return -1;
            } else {
                return right.search(key);
            }
        }else{
            if (left==null){
                setTime(System.currentTimeMillis()-start);
                return -1;
            }else{
                return left.search(key);
            }
        }
    }
}
